package algorithm.t202112;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/12/16 19:19
 * @description :1道
 * 今天才发现，图论的知识也太可怕了，果然，算法这条路还是很长，今天早上34节课考了计算机专业英语（从10：20发卷子，11:20就收卷子，我还没写到作文就马上收卷
 ，唉，也是学生时代最后一次英语考试了，还行吧，还有就是本来今天的招聘会也因为疫情没举办，也不知道会延期到什么时候举办。还有就是西安的疫情这两天挺严重，请假
 又不好请了（本来上周问罗雄说的是今天这个招聘会结束就可以请假离校，但考试得来），本来计划这周六往房子搬东西，结果现在一看可能又得像公司那边申请延期了，很烦，再看吧，争取早点去实习，唉，转眼已经12月中旬了，距离跑城墙都过去了
 一个月，这时间也太快太快了，还记得老刘说的话：时间还有，前提是不浪费。珍惜时间，！干。
 persevere to last
 2021.12.16
 李红磊
 2021年12月16日21:15:07
 */
public class t20211216 {

    //743.网络延迟时间 Dijkstra
    public int networkDelayTime(int[][] times, int n, int k) {
        final int INF = Integer.MAX_VALUE / 2;

        int[][] g = new int[n][n];
        //建立邻接矩阵
        for (int i = 0; i < n; i++) {
            Arrays.fill(g[i], INF);
        }
        //对邻接矩阵赋值
        for (int[] t : times) {
            // 边序号从 0 开始
            int x = t[0] - 1, y = t[1] - 1, w = t[2];
            g[x][y] = w;
        }

        //从源点到某一点的距离数组
        int[] dist = new int[n];//dist[i]:表示源点到第i个点（下标从0开始）的最短路径
        Arrays.fill(dist, INF);
        dist[k - 1] = 0;//源点到源点本身的最短距离为0

        //最短路径是否被更新过
        boolean[] used = new boolean[n];

        for (int i = 0; i < n; i++) {
            //在未被确定最短路的点，寻找距离最小的点
            int x = -1;
            for (int y = 0; y < n; y++) {
                if (!used[y] && (x == -1 || dist[y] < dist[x])) {
                    x = y;
                }
            }

            used[x] = true;
            for (int j = 0; j < n; j++) {
                dist[j] = Math.min(dist[j], dist[x] + g[x][j]);
            }
        }

        //寻找所有到源点最短路径中的最大值
        int ans = Arrays.stream(dist).max().getAsInt();
        return ans == INF ? -1 : ans;

    }

    public static void main(String[] args) {
        t20211216 t20211216 = new t20211216();
        System.out.println(t20211216.networkDelayTime(new int[][]{
                {2, 1, 1},
                {2, 3, 1},
                {3, 4, 1}

        }, 4, 2));


    }


}
